package com.peng.leetcode.tree;

/**
 * LowestCommonAncestorByDfs
 * <p>
 * Created on 2022/11/27
 *
 * @author lupeng
 */
public class LowestCommonAncestorByDfs {

    public static void main(String[] args) {
        Integer[] arr = new Integer[] {3,5,1,6,2,0,8,null,null,7,4};
        //5
        //1
        TreeNode treeNode = TreeMain.array2tree(arr);
        System.out.println(new LowestCommonAncestorByDfs().lowestCommonAncestor(treeNode, new TreeNode(5), new TreeNode(1)));
    }

    TreeNode ancestor;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfsFind(root, p, q);
        return ancestor;
    }

    private void dfsFind(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || ancestor != null) {
            return;
        }
        dfsFind(root.left, p, q);
        dfsFind(root.right, p, q);
        if (isAncestor(root, p) && isAncestor(root, q) && ancestor == null) {
            ancestor = root;
        }
    }

    private boolean isAncestor(TreeNode root, TreeNode target) {
        if (root == null) {
            return false;
        }
        if (root.val == target.val) {
            return true;
        }
        return isAncestor(root.left, target) || isAncestor(root.right, target);
    }
}
